package com.base.dynamicprograming;

import java.util.Arrays;

/**
 * 629. K个逆序对数组
 *给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。
 *
 * 逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。
 *
 * 由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/k-inverse-pairs-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年11月11日 22:37
 */
public class KInversePairs {
    int mod = (int)1e9+7;
    public int kInversePairs(int n, int k) {
        int[][] f = new int[n + 1][k + 1];

        f[1][0] = 1;
        for (int i = 2; i <= n; i++) {
            f[i][0] = 1;
            for (int j = 1; j <= k; j++) {
               int tmp = (f[i][j-1]+f[i-1][j]) % mod;
               if (j>=i){
                   tmp -= f[i-1][j-i];
               }
               tmp = tmp<0?(tmp+mod)%mod:tmp>mod?tmp%mod:tmp;
               f[i][j] =tmp;
            }

        }
        return f[n][k];
    }

    public static void main(String[] args) {
        System.out.println(new KInversePairs().kInversePairs(3,2));
    }
}
